class Solution {
public:
    int mostProfitablePath(vector<vector<int>>& edges, int bob, vector<int>& amount) {
        int n = amount.size();
        vector<int> e[n];
        for (auto &edge : edges) {
            e[edge[0]].push_back(edge[1]);
            e[edge[1]].push_back(edge[0]);
        }

        int pa[n], A[n], B[n];
        function<void(int, int, int)> dfs1 = [&](int sn, int fa, int d) {
            pa[sn] = fa;
            A[sn] = d;
            for (int fn : e[sn]) if (fn != fa) dfs1(fn, sn, d + 1);
        };
        dfs1(0, -1, 0);

        for (int i = 0; i < n; i++) B[i] = n + 1;
        for (int sn = bob, i = 0; sn >= 0; sn = pa[sn], i++) B[sn] = i;

        int ans = -2e9;
        function<void(int, int)> dfs2 = [&](int sn, int tot) {
            if (A[sn] < B[sn]) tot += amount[sn];
            else if (A[sn] == B[sn]) tot += amount[sn] / 2;
            int ch = 0;
            for (int fn : e[sn]) if (fn != pa[sn]) {
                ch++;
                dfs2(fn, tot);
            }
            if (ch == 0) ans = max(ans, tot);
        };
        dfs2(0, 0);
        return ans;
    }
};


